//
// Created by shenbin on 2022/5/10.
// https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
//

#ifndef ALGORITHM_TRAINNING_C05_LC429_H
#define ALGORITHM_TRAINNING_C05_LC429_H
#include <vector>
#include <queue>
using namespace std;
class LeetCode429 {
public:
    vector<vector<int>> levelOrder(Node* root){
        if(root == nullptr) return {};
        vector<vector<int>> ans;
        queue<pair<Node*, int>> q;
        q.push(make_pair(root, 0));
        while(!q.empty()){
            Node* node = q.front().first;
            int depth = q.front().second;
            q.pop();
            if (depth >= ans.size()) ans.push_back({});
            ans[depth].push_back(node->val);
            for(Node* child:node->children){
                q.push(make_pair(child, depth));
            }
        }
        return ans;

    }
private:
    struct Node {
        int val;
        vector<Node *> children;

        Node() {}

        Node(int _val) {
            val = _val;
        }

        Node(int _val, vector<Node *> _children) {
            val = _val;
            children = _children;
        }
    };
};

#endif //ALGORITHM_TRAINNING_C05_LC429_H
